// https://leetcode.cn/problems/evaluate-boolean-binary-tree/

// 题干：给你一棵 完整二叉树 的根，这棵树有以下特征：
//    叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
//    非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
//       计算 一个节点的值方式如下：
//          如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
//          否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算 。
//          返回根节点 root 的布尔运算值。
//          完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
//          叶子节点 是没有孩子的节点。

// 示例：输入：root = [2,1,3,null,null,0,1]
//       输出：true

// 碎语：既要宏观也要微观，注意到最后到叶子节点直接返回其值即可，不用到空节点
//       从下至上，是后续遍历

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    bool evaluateTree(TreeNode* root)
    {
        if (root->left == nullptr) return root->val; // 因为是完整二叉树，所以选取一个分支即可

        // 申请两个变量来记录左右两边的布尔值
        bool leftTree = evaluateTree(root->left);
        bool rightTree = evaluateTree(root->right);

        if (root->val == 2) return leftTree | rightTree;
        else return leftTree & rightTree;
    }
};

int main()
{
    // 示例：输入：root = [2,1,3,null,null,0,1]
    Solution sol;

    auto root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(1);

    cout << sol.evaluateTree(root) << " ";
    cout << endl;

    return 0;
}